Trên bước đường cầu đạo, ông cùng Xá-lợi-phất đã thỉnh giáo nhiều đạo sĩ cao nhân, tiếp thu nhiều tư tưởng triết học khác nhau. Một số chủ trương hẳn thuyết Vô Ðạo Ðức (đạo đức là sự vô ích) một số khác đề cao thuyết Ðịnh Mệnh, và một số khác truyền bá tư tưởng Duy vật. Tuy nhiên, cả hai đều tìm ra những khiếm khuyết của các giáo thuyết, vì vậy không để tâm nghiên cứu và tiếp tục tìm kiếm.

Vào khi cả Mục-kiền-liên và Xá-lợi-phất đã khoảng bốn mươi tuổi, bấy giờ, Phật Thích-ca Mâu-ni vừa cho phép đoàn đệ tử đầu tiên gồm 60 người, đều là những người biết nhiều hiểu rộng, khai môn thực hiện việc truyền bá giáo lý trong dân chúng[3]. Riêng Đức Phật thì đích thân đến thành Vương Xá (Rājagaha) để tiếp độ vị vua nước Ma-kiệt-đà tên là Tần-bà-sa-la (Bimbisara) và nhận lãnh ngôi Tịnh xá Trúc Lâm (Veluvana Vihàra) do vua dâng cúng.

Khi Phật đang có mặt tại ngôi chùa này thì Mục-kiền-liên và Xá-lợi-phất vừa quay về thành Vương Xá, tạm thời ngụ trong viện của Đạo sĩ Sànjaya. Một lần khi ra phố, Xá-lợi-phất vô tình gặp gỡ với Trưởng lão A-thuyết-thị (tiếng Pali: Assaji, tiếng Phạn: Asvajit), một trong những vị đệ tử đầu tiên của Phật Thích Ca. Được Assaji khai ngộ về khái niệm Tứ diệu đế, Xá-lợi-phất liền đắc Pháp nhãn (Dhamma Cakkhu) trong tâm thức chứng quả Nhập Lưu, Tu Ðà Hườn (Sotàpatti). Sau khi về nơi trọ, ông thuật lại cho Mục-kiền-liên nghe.

Cũng như Xá-lợi-phất, Mục-kiền-liên nhanh chóng giác ngộ con đường đạo mà ông tìm kiếm bấy lâu nay. Từ đó, 2 ông kiên định con đường đạo, gia nhập Tăng đoàn và trở thành một trong những Thánh nhân nổi tiếng bật nhất được ghi nhận trong Lịch sử Phật giáo.